package buckets.strategies;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import buckets.core.BucketsInstance;
import buckets.core.BucketState;

/**
 * Search space support - e.g. expanding states, investigation of state for being target
 * or backtracking resulted path.
 * 
 * @author vasek
 *
 */
public class SearchSpaceSupport {
	
	protected BucketsInstance instance;
	protected LinkedList<BucketState> path = new LinkedList<BucketState>();
	protected int statesCounter = 0;

	/**
	 * Constructor.
	 * 
	 * @param instance which is being solved
	 */
	public SearchSpaceSupport(final BucketsInstance instance) {
		super();
		this.instance = instance;
	}


	/**
	 * Gets neighbors of particular state. These neighbors should be obtained applying
	 * transformations on current state.
	 * 
	 * @param state that is expanded
	 * @return one particular state's neighbors
	 */
	protected List<BucketState> expand(final BucketState state) {
		final List<BucketState> expanded = new ArrayList<BucketState>();
		final int[] bucketsCurrent = state.getConfiguration();
		final int[] capacities = instance.getCapacities();
		
		/**
		 * We can flush each bucket.
		 */
		for (int i = 0; i < bucketsCurrent.length; i++) {
			final int[] bucketsNew = bucketsCurrent.clone();
			bucketsNew[i] = 0;
			final BucketState neighbor = new BucketState(bucketsNew);
			expanded.add(neighbor);
		}
		
		/**
		 * We can fill each bucket if it's empty.
		 */
		for (int i = 0; i < bucketsCurrent.length; i++) {
			if (bucketsCurrent[i] == 0) {
				final int[] bucketsNew = bucketsCurrent.clone();
				bucketsNew[i] = capacities[i];
				final BucketState neighbor = new BucketState(bucketsNew);
				expanded.add(neighbor);
			}
		}
		
		/**
		 * Or we can transfuse each bucket with at least something to each other.
		 */
		for (int from = 0; from < bucketsCurrent.length; from++) {
			for (int to = 0; to < bucketsCurrent.length; to++) {
				
				if (from == to) {
					continue;
				}
				
				if (bucketsCurrent[from] > 0) {
					final int complement = capacities[to] - bucketsCurrent[to];
					if (complement > 0) {
						final int[] bucketsNew = bucketsCurrent.clone();
						bucketsNew[to] += (bucketsNew[from] < complement) ? bucketsNew[from] : complement;
						bucketsNew[from] -= (bucketsNew[from] < complement) ? bucketsNew[from] : complement;
						final BucketState neighbor = new BucketState(bucketsNew);
						if (!neighbor.equals(state)) {
							expanded.add(neighbor);
						}
					} 
				} else {
					break;
				}
			}
		}
		
		
		return expanded;
	}
	
	/**
	 * For a specified state it backtrack thought it's predecessors to start node.
	 * 
	 * @param state particular state
	 * @return path from the start to the specified state
	 */
	protected List<BucketState> backtrackToStart(BucketState state) {
		final LinkedList<BucketState> path = new LinkedList<BucketState>();
		path.addFirst(state);
		
		while (!(state.equals(new BucketState(instance.getOriginalCapacities())))) {			
			state = state.getPredecessor();
			path.addFirst(state);
		}
		
		return path;
	}
	

	/**
	 * Whether state is a target state.
	 * 
	 * @param state tested state
	 * @return true if state is a target state, false otherwise
	 */
	protected boolean isTarget(final BucketState state) {				
		return state.equals(new BucketState(instance.getTargetCapacities()));
	}
}
